{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/rec_system_logo.jpg\">\n",
    "<center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import warnings\n",
    "\n",
    "warnings.simplefilter('ignore')\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.base import BaseEstimator\n",
    "from sklearn.metrics import mean_squared_error\n",
    "from sklearn.metrics.pairwise import cosine_similarity\n",
    "from tqdm import tqdm_notebook\n",
    "\n",
    "%pylab inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В данной статье мы разберём простейшие алгоритмы рекомендательных систем.\n",
    "\n",
    "Рекомендательные системы используются повсеместно:\n",
    "1. Онлайн-кинотеатры используют их чтобы предлагать пользователям новые фильмы.\n",
    "2. Социальные сети предлагают новых друзей или формируют ленту на основе ваших предпочтений.\n",
    "3. Музыкальные сервисы, онлайн-радио подбирают музыку специально для вас.\n",
    "4. Интернет-магазины предлагают товары пользователям, которые могут их заинтересовать.\n",
    "\n",
    "Рассмотрим построение такой системы на датасете от `GroupLens` $-$ [`MovieLens`](https://grouplens.org/datasets/movielens/):\n",
    "Это набор данных из $27 000$ фильмов и $138 000$ пользователей, с общим количеством оценок в $20$ миллионов.\n",
    "\n",
    "Но мы воспользуемся уменьшенной версией для быстроты вычислений: $9 000$ фильмов, $700$ пользователей, $100 000$ оценок.\n",
    "Скачать напрямую датасет можно по этой [ссылке](http://files.grouplens.org/datasets/movielens/ml-latest-small.zip)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# для UNIX систем\n",
    "!wget http://files.grouplens.org/datasets/movielens/ml-latest-small.zip\n",
    "!unzip ml-latest-small.zip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Для начала немного посмотрим на данные\n",
    "- `links.csv` $-$ связь между `id` фильма в датасете и `id` соответствующего фильма на `imdb.com` и `themoviedb.org`;\n",
    "- `movies.csv` $-$ описание каждого фильма с его названием и жанрами;\n",
    "- `ratings.csv` $-$ оценки пользователей фильмов с временной отметкой;\n",
    "- `tags.csv` $-$ список тегов, которые поставил пользователь фильму, с временной отметкой.\n",
    "\n",
    "Для данной задачи нам понадобятся только часть данных $-$ информация о том, какой рейтинг ставили пользователи фильмам."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ratings = pd.read_csv('./ml-latest-small/ratings.csv', parse_dates=['timestamp'])\n",
    "ratings.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### О метрике\n",
    "Для рекомендательных систем используются стандартные метрики: `MSE`, `MAE` и `RMSE`.\n",
    "\n",
    "Мы воспользуемся `RMSE`: классическая метрика для задач рекомендации после прошедшего [Netflix Prize](https://ru.wikipedia.org/wiki/Netflix_Prize). Хотя и у неё есть свои минусы, например:\n",
    "- Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки (предсказание 10 вместо 7 хуже, чем предсказать 4 вместо 1);\n",
    "- Помимо предсказания рейтинга очень важно подать пользователю фильмы в нужном порядке, то есть необходимо учитывать и ранжирование, что данная метрика не умеет.\n",
    "\n",
    "Так же сразу отложим часть выборки для тестирования модели по принципу: для каждого пользователя отрежем последние 20% оценок."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rmse = lambda y_true, y_pred: np.sqrt(mean_squared_error(y_true, y_pred))\n",
    "\n",
    "def train_test_split(X, ratio=0.2, user_col='userId', item_col='movieId',\n",
    "                     rating_col='rating', time_col='timestamp'):\n",
    "    # сортируем оценки по времени\n",
    "    X.sort_values(by=[time_col], inplace=True)\n",
    "    # список всех юзеров\n",
    "    userIds = X[user_col].unique()\n",
    "    X_train_data = []\n",
    "    X_test_data = []\n",
    "    y_train = []\n",
    "    y_test = []\n",
    "    for userId in tqdm_notebook(userIds):\n",
    "        curUser = X[X[user_col] == userId]\n",
    "        # определяем позицию, по которой делим выборку и размещаем данные по массивам\n",
    "        idx = int(curUser.shape[0] * (1 - ratio))\n",
    "        X_train_data.append(curUser[[user_col, item_col]].iloc[:idx, :].values)\n",
    "        X_test_data.append(curUser[[user_col, item_col]].iloc[idx:, :].values)\n",
    "        y_train.append(curUser[rating_col].values[:idx])\n",
    "        y_test.append(curUser[rating_col].values[idx:])\n",
    "    # cтекуем данные по каждому пользователю в общие массивы\n",
    "    X_train = pd.DataFrame(np.vstack(X_train_data), columns=[user_col, item_col])\n",
    "    X_test = pd.DataFrame(np.vstack(X_test_data), columns=[user_col, item_col])\n",
    "    y_train = np.hstack(y_train)\n",
    "    y_test = np.hstack(y_test)\n",
    "    return X_train, X_test, y_train, y_test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train.shape, len(y_train), X_test.shape, len(y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Формализуем задачу\n",
    "Имеется множество пользователей ($U$) и множество фильмов ($I$). Для некоторых фильмов конкретный пользователь уже поставил оценку ($r_{ui}$), надо предсказать оценку для определённых фильмов.\n",
    "\n",
    "Например, есть таблица с оценками пользоватей:\n",
    "<center>\n",
    "<img src=\"../../img/ratings.png\" width=70%>\n",
    "<center>\n",
    "    \n",
    "А нам нужно как можно точнее предсказать оценки под знаком вопроса:\n",
    "<center>\n",
    "<img src=\"../../img/ratings_predict.png\" width=70%>\n",
    "<center>\n",
    "\n",
    "Для того, чтобы получить рекомендации для пользователя можно предсказать все оценки и вернуть лучшие из них."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# User-based model\n",
    "\n",
    "`user-based model` является моделью коллабораивной фильтрации, основная идея которой:\n",
    "> похожим пользователям обычно нравятся похожие объекты\n",
    "\n",
    "Определять схожесть $2$ пользователей будем с помощью корреляции Пирсона между векторами уже поставленными оценками, этот показатель хорош тем, что учитывает несколько важных ньюансов:\n",
    "1. Два различных пользователя могут иметь мало общих фильмов, но при этом корреляция показывает большую схожесть, а иногда и вовсе $1$. Чтобы избежать этого давайте в числителе считать только общий рейтинг, а знаменатель оставим по всем рейтингам;\n",
    "2. Для двух различных пользователей оценка может иметь различный вес, так для одного средний фильм имеет рейтинг $2$, а для другого $4$. Такие пользователи похожи, но корреляция скажет, что они различны. Чтобы устранить это, давайте из всех оценок пользователя вычтем его среднюю оценку.\n",
    "\n",
    "Таким образом итоговая формула схожести двух пользователей вычисляется по формуле:\n",
    "$$\n",
    "    \\textit{sim(u, v)} = \\frac\n",
    "    {\\sum_i{\\big((r_{ui} - \\overline{r_u}) \\times (r_{vi} - \\overline{r_v})\\big)}}\n",
    "    {\\sqrt{\\sum_i{(r_{ui} - \\overline{r_u})^2}} \\times \\sqrt{\\sum_i{(r_{vi} - \\overline{r_v})^2}}}\n",
    "$$\n",
    "\n",
    "Интуитивно понятно, что предпологаемый рейтинг для пользователя можно оценить как средний рейтинг между схожими пользователями, но, благодаря введению понятия схожести, можно улучшить эту оценку, ведя взвешенные веса и учитывая всех пользователей, которые посмотрели этот фильм:\n",
    "$$\n",
    "    r_{ui} = \\overline{r_v} + \\frac\n",
    "    {\\sum_{v \\in User_i}\\big(\\textit{sim(u, v)} \\times (r_{vi} - \\overline{r_v})\\big)}\n",
    "    {\\sum_{v \\in User_i}\\textit{sim(u, v)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UserBased(BaseEstimator):\n",
    "    def fit(self, X, y, user_col='userId', item_col='movieId'):\n",
    "        X = X.copy()\n",
    "        # сохраним текущих пользователей и имеющиеся предметы\n",
    "        self.users = X[user_col].unique()\n",
    "        self.items = X[item_col].unique()\n",
    "        \n",
    "        X['y'] = y\n",
    "        # рассчитаем среднее значение рейтинга для пользователя и предмета\n",
    "        self.mean_y_user = X.groupby(user_col)['y'].mean()\n",
    "        self.mean_y_item = X.groupby(item_col)['y'].mean()\n",
    "        \n",
    "        # вычитаем среднюю оценку пользователя\n",
    "        X['y'] -= X[user_col].apply(lambda x: self.mean_y_user[x])\n",
    "        \n",
    "        # создаём векторы для каждого пользователя из просмотренных фильмов\n",
    "        # для неизвестных фильмов ставим оценку 0\n",
    "        self.user_ratings = pd.pivot_table(X, values='y', index=user_col,\n",
    "                                           columns=item_col, fill_value=0)\n",
    "        \n",
    "        # считаем попарную схожесть между юзерами\n",
    "        self.user_sim = cosine_similarity(self.user_ratings)\n",
    "        \n",
    "        # также сделаем словарь - {значение user_col: index в user_ratings}\n",
    "        self.user_pos = dict()\n",
    "        for user in self.users:\n",
    "            self.user_pos[user] = np.argwhere(self.user_ratings.index.values == user)[0][0]\n",
    "        return self\n",
    "    \n",
    "    def predict_rating(self, pr_user, pr_item):\n",
    "        # если в обучающей выборке нет такого предмета\n",
    "        # или пользователя, то вернём 0\n",
    "        if not pr_item in self.items or not pr_user in self.users:\n",
    "            return 0\n",
    "        \n",
    "        # считаем числитель и знаменатель дроби из формулы предсказания\n",
    "        numerator = self.user_sim[self.user_pos[pr_user]].dot(\n",
    "                        self.user_ratings.loc[:, pr_item])   \n",
    "        # вычитаем 1, так как схожесть пользователя с самим собой равна 1,\n",
    "        # но модель не должна это учитывать\n",
    "        denominator = self.user_sim[self.user_pos[pr_user]].sum() - 1\n",
    "        \n",
    "        return self.mean_y_user[pr_user] + numerator / denominator\n",
    "    \n",
    "    def predict(self, X, user_col='userId', item_col='movieId'):\n",
    "        y = X[[user_col, item_col]].apply(lambda row: self.predict_rating(row[0], row[1]), axis=1)\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "print('start fitting...')\n",
    "ub = UserBased().fit(X_train, y_train)\n",
    "print('start predicting...')\n",
    "print('rmse = {}'.format(rmse(y_test, ub.predict(X_test))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как можно заметить, такой подход влечёт несколько проблем $-$ при увелечение количества предметов растёт сложность вычисления схожести, а значит и время работы, так же при большом количестве предметов данные получаются очень разреженные, поэтому пользователь даже не узнает про часть товара, хотя там могут быть и интересные ему."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Item-based model\n",
    "`item-based model` очень похожа на предыдущую модель по структуре, но теперь мы ищем похожие товары, а не пользователей.\n",
    "\n",
    "Поэтому при вычисление $r_{ui}$ мы посмотрим на все фильмы пользователя $u$, оценим их схожесть с фильмом $i$ и посчитаем взвешенную сумму:\n",
    "$$\n",
    "    r_{ui} = \\overline{r_i} + \\frac\n",
    "    {\\sum_{j \\in Item_u}\\big(\\textit{sim(i, j)} \\times (r_{uj} - \\overline{r_j})\\big)}\n",
    "    {\\sum_{j \\in Item_u}\\textit{sim(i, j)}}\n",
    "$$\n",
    "\n",
    "Оценивать же схожесть двух фильмов будем с помощью той же корреляции Пирсона:\n",
    "$$\n",
    "    \\textit{sim(i, j)} = \\frac\n",
    "    {\\sum_u{\\big((r_{ui} - \\overline{r_i}) \\times (r_{uj} - \\overline{r_j})\\big)}}\n",
    "    {\\sqrt{\\sum_u{(r_{ui} - \\overline{r_i})^2}} \\times \\sqrt{\\sum_u{(r_{uj} - \\overline{r_j})^2}}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ItemBased(BaseEstimator):\n",
    "    def fit(self, X, y, user_col='userId', item_col='movieId'):\n",
    "        X = X.copy()\n",
    "        # сохраним текущих пользователей и имеющиеся предметы\n",
    "        self.users = X[user_col].unique()\n",
    "        self.items = X[item_col].unique()\n",
    "        \n",
    "        X['y'] = y\n",
    "        # рассчитаем среднее значение рейтинга для пользователя и предмета\n",
    "        self.mean_y_user = X.groupby(user_col)['y'].mean()\n",
    "        self.mean_y_item = X.groupby(item_col)['y'].mean()\n",
    "        \n",
    "        # вычитаем среднюю оценку предмета\n",
    "        X['y'] -= X[item_col].apply(lambda x: self.mean_y_item[x])\n",
    "        \n",
    "        # создаём векторы для каждого фильма с оценками пользователя\n",
    "        # если пользователь не поставил оценку, то ставим 0\n",
    "        self.item_ratings = pd.pivot_table(X, values='y', index=item_col,\n",
    "                                           columns=user_col, fill_value=0)\n",
    "        \n",
    "        # считаем попарную схожесть между фильмами\n",
    "        self.item_sim = cosine_similarity(self.item_ratings)\n",
    "        \n",
    "        # также сделаем словарь {значение item_col: index в item_ratings}\n",
    "        self.item_pos = dict()\n",
    "        for item in self.items:\n",
    "            self.item_pos[item] = np.argwhere(self.item_ratings.index.values == item)[0][0]\n",
    "        return self\n",
    "    \n",
    "    def predict_rating(self, pr_user, pr_item):\n",
    "        # если в обучающей выборке нет такого предмета\n",
    "        # или пользователя, то вернём 0\n",
    "        if not pr_item in self.items or not pr_user in self.users:\n",
    "            return 0\n",
    "        \n",
    "        # считаем числитель и знаменатель дроби из формулы предсказания\n",
    "        numerator = self.item_sim[self.item_pos[pr_item]].dot(\n",
    "                        self.item_ratings.loc[:, pr_user])   \n",
    "        # вычитаем 1, так как схожесть предмета с самим собой равна 1,\n",
    "        # но модель не должна это учитывать\n",
    "        denominator = self.item_sim[self.item_pos[pr_item]].sum() - 1\n",
    "        \n",
    "        return self.mean_y_item[pr_item] + numerator / denominator\n",
    "    \n",
    "    def predict(self, X, user_col='userId', item_col='movieId'):\n",
    "        y = X[[user_col, item_col]].apply(lambda row: self.predict_rating(row[0], row[1]), axis=1)\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "print('start fitting...')\n",
    "ib = ItemBased().fit(X_train, y_train)\n",
    "print('start predicting...')\n",
    "print('rmse = {}'.format(rmse(y_test, ib.predict(X_test))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы окончательно понять суть этих двух моделей, вот замечательная картинка:\n",
    "<center>\n",
    "<img src=\"../../img/based_filtering.jpg\" width=70%>\n",
    "<center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как можно заметить данные алгоритмы имеют общие недостатки, например:\n",
    "1. Холодный запуск, когда у нас нет информации о пользователе или товаре, то система не может предсказать рейтинг, мы возвращали в таких ситуациях 0, но, как вариант, можно возвращать среднюю оценку пользователя или среднюю оценку предмета, что уже даст хороший прирост в качестве.\n",
    "2. Для нетипичных пользователей или предметов сложно дать объективные предсказания, так как они мало похожи на остальных.\n",
    "\n",
    "Конечно это далеко не все алгоритмы построения рекомендательных систем, существуют более простые, один из них $-$ Most Popular, который просто возвращает наиболее популярные товары в сервисе, но которые пользователь ещё не видел, так и более сложные, например, SVD, который использует возможность сингулярного разложения матрицы пользователь-предмет, что позволяет выявлять какие-то скрытые параметры, например, как пол влияет на рейтинг и т.д.\n",
    "Помимо коллаборативная фильтрации, существуют и другие принципы:\n",
    "- Контентная фильтрация $-$ формирует рекомендацию на основе поведения пользователя, для решения подобных задач можно использовать, например, факторизационные машины;\n",
    "- Смешанные подходы $-$ объединяют в себе content based и collaborative фильтрации.\n",
    "\n",
    "Полезные ссылки:\n",
    "- [Теоритическая статья от Яндекс](https://habrahabr.ru/company/yandex/blog/241455/);\n",
    "- [Про различные алгоритмы от ibm](https://www.ibm.com/developerworks/ru/library/os-recommender1/index.html);\n",
    "- [Серия статей на medium, но код плохо оформлен](https://medium.com/@tomar.ankur287).\n",
    "\n",
    "На этом всё, если у вас есть какие-то вопросы или замечания, то вы можете найти меня в `slack` $-$ `spirin.egor` или написать на почту $-$ `egor@spirin.tech`."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
